﻿//303. 区域和检索 - 数组不可变
//给定一个整数数组  nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
//实现 NumArray 类：
//NumArray(int[] nums) 使用数组 nums 初始化对象
//int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

// 动态规划思想解

namespace LeetCode.DynamicProgramming
{
    public class LeetCode_303 
    {
        public class NumArray
        {
            int[] sums;
            public NumArray(int[] nums)
            {
                if (nums.Length == 0)
                {
                    sums = new int[] { 0 };
                    return;
                }
                sums = new int[nums.Length];
                sums[0] = nums[0];
                for (int i = 1; i < nums.Length; i++)
                {
                    sums[i] = nums[i] + sums[i - 1];
                }
            }

            public int SumRange(int left, int right)
            {
                if (left - 1 < 0)
                {
                    return sums[right];
                }
                return sums[right] - sums[left - 1];
            }
        }
    }
    /**
    * Your NumArray object will be instantiated and called as such:
    * NumArray obj = new NumArray(nums);
    * int param_1 = obj.SumRange(left,right);
    */
}
